package com.zjsru.plan2023.oneday;

import java.util.Arrays;

/**
 * @Author: CookLee
 * @Date: 2023/7/10
 *  最接近的三数之和
 * \
 *  输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 *\
 * 输入：nums = [0,0,0], target = 1
 * 输出：0
 */
public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        int best = Integer.MAX_VALUE;
        int ans = 0;
        if (nums.length < 3) {
            return -1;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int first = nums[i];
            //连续两个数一样则不计入
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //j代表第2个数,k代表第三个数
            for (int j = i + 1, k = nums.length - 1; j < k; ) {
                int second = nums[j];
                int third = nums[k];
                int sum = first + second + third;
                if (sum < target) {
                    j++;
                } else {
                    k--;
                }
                //差值越小说明越接近
                if (best >= Math.abs(sum - target)) {
                    best = Math.abs(sum - target);
                    ans = sum;
                }
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        ThreeSumClosest threeSumClosest = new ThreeSumClosest();
        int[] nums = new int[]{-1,2,1,-4};
        int target = 1;
        System.out.println(threeSumClosest.threeSumClosest(nums,target));
    }
    
}
